| class A_SEARCH{ETP,ATP<$ARR{ETP}} |
|---|
| **** | Searching algorithms on arrays. Note that the element comparison is defined here bu the percondition checks may use a different lt when calling the is_sorted routine in A_SORT |
| COMPARE{_} |
| binary_search(a: ATP,e: ETP): INT |
|---|
| binary_search(a: ATP,e:ETP,l,u: INT):INT |
|---|
| **** | Assuming self is sorted, return the index of the element preceding the first element greater than `e' according to `elt_lt' in the range [l,u]. -1 if all elements are greater than `e'. |
| binary_search(a: ATP,e:ETP,lt: ROUT{ETP,ETP}:BOOL,l,u: INT):INT |
|---|
| **** | Assuming self is sorted, return the index of the element preceding the first element greater than `e' according to `elt_lt' in the range [l,u]. -1 if all elements are greater than `e'. |
| index_if(a: ATP,test:ROUT{ETP}:BOOL):INT |
|---|
| **** | Return the index of the leftmost element that satisfies `test', or -1 if there is none. |
| index_of(a: ATP, e: ETP): INT |
|---|
| **** | Return the index of the elemetn 'e' in 'a' Return -1 if the element is not found. Does not assume a is sorted |
| match_subarray(a: ATP, marr:ARRAY{ETP},l,u: INT):INT |
|---|
| **** | The index of the leftmost subarray of marr which matches 'a' Confine search to subrange [l,u] of a -1 if none. Uses simple algorithm which has good performance unless the arrays are special (eg. many repeated values). Also uses ARRAY{ETP} rather than a general $ARR since it will almost certainly be worthwhile to copy into a concrete class rather than use dispatching on the argument |
| check_range(a: ATP,l,u: INT): BOOL |
|---|
| is_sorted(a: ATP,l,u:INT): BOOL |
|---|